#include <stdio.h>
#include "seq_list.cpp"

// 题太多了 不抄了

// map法
// 存储每个元素出现的个数放入map 再遍历map 
// 时间O(n) 空间O(n)

// 排序法
// 先排序 若到中位 过半连续元素相等则为主元素
// 时间O(nlogn) 空间O(1)

// 摩尔投票法
// 时间O(n) 空间O(1)
int GetMainNum(SeqList L)
{
    int num = L.data[0], count = 1;
    for (int i = 1; i < L.length; i++)
    {
        if (num == L.data[i])
            count++;
        else if (--count == 0)
        {
            num = L.data[i];
            count = 1;
        }
    }

    count = 0;
    for (int i = 1; i < L.length; i++)
        if (L.data[i] == num)
            count++; 

    if (count > L.length/2)
        return num;
    
    return -1;
}

int main()
{
    SeqList L;
    int data[12] = {2,2,3,1,1,1,2,1,1,1,1,2};
    L.data = data;
    L.length = 12;

    int num = GetMainNum(L);
    printf("===> %d\n",num);
}